package problem96_Unique_Binary_Search_Trees;

/**
 * 对于有n个点的树，其二叉搜索树的个数为a[n]
 * 那么a[n]可以这样表示：
 * 左子树节点个数为0，右子树节点个数为n-1，此时二叉搜索树个数为a[0]*a[n-1]
 * 左子树节点个数为1，右子树节点个数为n-2，此时二叉搜索树个数为a[1]*a[n-2]
 * 左子树节点个数为2，右子树节点个数为n-3，此时二叉搜索树个数为a[2]*a[n-3]
 * ................................
 * 
 * 所以a[n] = sum(a[i]*a[n-1-i]) n-1>=i>=0;
 * 
 * @author Ivan
 *
 */
public class Solution {
	public int numTrees(int n) {
        int[] a=new int[n+1];
        a[0]=1;
        a[1]=1;
        for(int i=2;i<=n;i++){
        	for(int j=0;j<=i-1;j++){
        		a[i]+=a[j]*a[i-1-j];
        	}
        }
        return a[n];
    }
}
